//编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。 
//
// 示例: 
//
// 输入: 25
//输出: 9
//解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次) 
//
// 提示： 
//
// 
// n <= 10^9 
// 
// Related Topics递归 | 数学 | 动态规划 
//
// 👍 64, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;

class NumberOf2sInRangeLcci {
    public static void main(String[] args) {
        Solution solution = new NumberOf2sInRangeLcci().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private char[] s;
        int[][] memo;  // 备忘录

        // 数位DP:和https://leetcode.cn/problems/number-of-digit-one/submissions/一致
        public int numberOf2sInRange(int n) {
            s = String.valueOf(n).toCharArray();
            // 根据题目给出的范围，一个数中 1 的数量最多只有 10 种情况
            int m = s.length;
            memo = new int[m][10];
            // 为什么这么剪枝?
            // 例如：1 2 3
            // 0 0 1~9 和 0 9 1~9 着两种选择是相同的，可以通过位数表示
            // 但是 0 1 1~9 就不能单独的通过位数来表示了
            // 所以我们还要添加一个维度，就是1的数量来标识，才不会混乱
            for (int i = 0; i < m; i++) {
                Arrays.fill(memo[i], -1);
            }
            return dfs(0, 0, true);
        }

        public int dfs(int i, int twoCnt, boolean isLimit) {
            if (i == s.length) return twoCnt;

            if (!isLimit && memo[i][twoCnt] != -1) return memo[i][twoCnt];

            // 根据isLimit来判断是否选择
            int up = isLimit ? s[i] - '0' : 9;
            int res = 0;
            // 进行递归
            for (int j = 0; j <= up; j++) {
                res += dfs(i + 1, twoCnt + (j == 2 ? 1 : 0), isLimit && j == up);
            }

            if (!isLimit) memo[i][twoCnt] = res;
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
